package leetcode.code1254;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

import leetcode.IDebug;
import leetcode.helper.H;

public class Solution2 implements IDebug {

	int[] p;
	boolean[] ok;

	public void init(int size) {
		p = new int[size];
		for (int i = 0; i < p.length; i++) {
			p[i] = i;
		}
		ok = new boolean[size];
		Arrays.fill(ok, true);
	}

	public void union(int a, int b) {
		ok[find(b)] = ok[find(a)] && ok[find(b)];
		p[find(a)] = find(b);
	}

	public int find(int id) {
		if (p[id] != id) {
			p[id] = this.find(p[id]);
		}
		return p[id];
	}

	public int index(int i, int j, int n) {
		return i * n + j;
	}

	public int closedIsland(int[][] grid) {
		int m = grid.length, n = grid[0].length;
		int size = m * n;
		this.init(size);
		ok[0] = false;
		// 合并第一行
		for (int i = 1; i < n; i++) {
			ok[this.index(0, i, n)] = false;
			ok[this.index(m - 1, i, n)] = false;
			if (grid[0][i] == grid[0][i - 1]) {
				this.union(this.index(0, i, n), this.index(0, i - 1, n));
			}
		}
		// 合并第一列
		for (int i = 1; i < m; i++) {
			ok[this.index(i, 0, n)] = false;
			ok[this.index(i, n - 1, n)] = false;
			if (grid[i][0] == grid[i - 1][0]) {
				this.union(this.index(i, 0, n), this.index(i - 1, 0, n));
			}
		}
		// 合并一般位置
		for (int i = 1; i < m; i++) {
			for (int j = 1; j < n; j++) {
				if (grid[i][j] == grid[i][j - 1]) {
					this.union(this.index(i, j, n), this.index(i, j - 1, n));
				}
				if (grid[i][j] == grid[i - 1][j]) {
					this.union(this.index(i, j, n), this.index(i - 1, j, n));
				}
			}
		}
		// 收集答案
		Set<Integer> set = new HashSet<>();
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				int cur = grid[i][j];
				int p = find(this.index(i, j, n));
				if (cur == 0 && ok[p]) {
					set.add(p);
				}
			}
		}
		return set.size();
	}

	@Override
	public void debug4() {
		H.compare(5, this.closedIsland(H.str2array1(
				"[[0,0,1,1,0,1,0,0,1,0],[1,1,0,1,1,0,1,1,1,0],[1,0,1,1,1,0,0,1,1,0],[0,1,1,0,0,0,0,1,0,1],[0,0,0,0,0,0,1,1,1,0],[0,1,0,1,0,1,0,1,1,1],[1,0,1,0,1,1,0,0,0,1],[1,1,1,1,1,1,0,0,0,0],[1,1,1,0,0,1,0,1,0,1],[1,1,1,0,1,1,0,1,1,0]]")));

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution2 so = new Solution2();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
